In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Byteasar loved to play with building blocks as a child.
He used to arrange the blocks into columns of random height
and then organize them in the following manner:
Byteasar would choose a number
and try to arrange the blocks in such a way that
some
consecutive columns would be of equal height. Furthermore he always tried to
achieve this goal in a minimum number of moves possible, where a single move consists in:
However, Byteasar was never quite sure if his sequence of moves was indeed optimal, therefore he has asked you to write a programme that will help him solve the problem.
Write a programme that:
In the first line of the standard input there are
two integers, and
(
), separated by a single space.
Each of the following
lines contains the height of some column;
the line no.
contains the integer
- the height of the
column,
ie. the number of blocks it consists of.
The optimal solution should be written out to the standard output, ie. such arrangement of blocks that:
For the input data:
5 3 3 9 2 3 1
the correct result is:
2 3 9 2 2 2
Task author: Tomasz Walen.